#include <bits/stdc++.h>
#define gc getchar
#define pc putchar
#define pt printf
#define IL inline
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rof(i,a,b) for(int i=a;i>=b;++i) 
using namespace std;
const int Mxk=4e6+5;
int P,T,N,M,K,Ans,Sum,C[Mxk];
int _() {
	int x=0,f=0;char ch=gc();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return f?-x:x;
}
void __(int x) {
	int stk[30],tp=0;
	if(x<0) x=-x,pc('-');
	do stk[++tp]=x%10,x/=10;while(x);
	while(tp) pc(stk[tp--]^48);
}
int Power(int x,int b) {
	int s=1;
	while(b) {
		if(b&1) (s*=x)%=P;
		(x*=x)%=P,b>>=1; 
	}
	return s;
}
void Upd(int &x,int y) {x=x+y<P?x+y:x+y-P;}
void DFS(int x,int s) {
	if(x>N) {C[s]++;return ;}
	For(i,0,M) DFS(x+1,s+i);
}
/*
998244353
3
1 2
3 4
25 25

*/
signed main() {//10
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	P=_(),T=_();
	while(T--) {
		N=_(),M=_(),K=N*M;
		Ans=Sum=0;
		For(i,0,K) C[i]=0;
		DFS(1,0);
		For(i,0,K) {
			Upd(Ans,C[i]*Sum%P),Upd(Sum,C[i]);
		}
		int Tot=Power(M+1,N<<1);
		__(Ans*Power(Tot,P-2)%P),pc('\n');
	}
	return 0;
}
